๋ฌธ์
๊ทธ๋ํ์ ์ ์ ์ ์งํฉ์ ๋๋ก ๋ถํ ํ์ฌ, ๊ฐ ์งํฉ์ ์ํ ์ ์ ๋ผ๋ฆฌ๋ ์๋ก ์ธ์ ํ์ง ์๋๋ก ๋ถํ ํ ์ ์์ ๋, ๊ทธ๋ฌํ ๊ทธ๋ํ๋ฅผ ํน๋ณํ ์ด๋ถ ๊ทธ๋ํ (Bipartite Graph) ๋ผ ๋ถ๋ฅธ๋ค.
๊ทธ๋ํ๊ฐ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ก์ ๋, ์ด ๊ทธ๋ํ๊ฐ ์ด๋ถ ๊ทธ๋ํ์ธ์ง ์๋์ง ํ๋ณํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
- ์ ๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ ์คํธ ์ผ์ด์ค๋ก ๊ตฌ์ฑ๋์ด ์๋๋ฐ, ์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ K๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ๊ทธ๋ํ์ ์ ์ ์ ๊ฐ์ V์ ๊ฐ์ ์ ๊ฐ์ E๊ฐ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์์๋๋ก ์ฃผ์ด์ง๋ค. ๊ฐ ์ ์ ์๋ 1๋ถํฐ V๊น์ง ์ฐจ๋ก๋ก ๋ฒํธ๊ฐ ๋ถ์ด ์๋ค. ์ด์ด์ ๋์งธ ์ค๋ถํฐ E๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ์ ์ ๋ํ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋๋ฐ, ๊ฐ ์ค์ ์ธ์ ํ ๋ ์ ์ ์ ๋ฒํธ u, v (u โ v)๊ฐ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
- K๊ฐ์ ์ค์ ๊ฑธ์ณ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ๊ทธ๋ํ๊ฐ ์ด๋ถ ๊ทธ๋ํ์ด๋ฉด YES, ์๋๋ฉด NO๋ฅผ ์์๋๋ก ์ถ๋ ฅํ๋ค.
๐ Logic
class Graph {
final List<Integer>[] graph;
final int[] Binary = { -1, 1 };
int[] discovered;
boolean isBinaryGraph = true;
int toggle = 0;
public Graph(int size) {
this.graph = new ArrayList[size+1];
discovered = new int[size+1];
for (int i = 0; i <= size; i++) {
graph[i] = new ArrayList<>();
}
}
}
- ๊ทธ๋ํ์ ์ ๋ณด๋ฅผ ์ ์ฅํ๊ธฐ ์ํ ํด๋์ค
public boolean solution() {
for (int i=1; i < graph.length; i++) {
if (graph[i].size() > 0 & discovered[i] == 0) {
isBinaryGraph = this.bfs(i);
if (!isBinaryGraph)
break;
}
}
return this.isBinaryGraph;
}
-
์ธ์ ์ ์ ์ ๋ณด๊ฐ ์๊ณ , ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ ๋ํด BFS ๋ฅผ ์ํ
- ์ ์ ์ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ (0: ๋ฏธ๋ฐฉ๋ฌธ), (-1: 1๊ทธ๋ฃน), (1: 2๊ทธ๋ฃน)
- ์ด๋ถ ๊ทธ๋ํ์ธ์ง๋ฅผ ์ ์ฅํ๋
isBinaryGraph์false๊ฐ ๋์ค๋ฉด ๋ ์ด์์ ํ์์ ์ข ๋ฃํ๊ณ ์ด๋ฅผ ๋ฐํ false๊ฐ ๊ณ์ ๋์ค์ง ์์ผ๋ฉด ์ด๋ถ ๊ทธ๋ํ์ด๋ฏ๋ก ์ด๊ธฐ๊ฐ์ธtrue๊ฐ ๋ฐํ
public boolean bfs(int parent) {
Queue<Integer> q = new LinkedList<>();
q.add(parent);
while (!q.isEmpty()) {
int now = q.poll();
if (discovered[now] == 0) { discovered[now] = Binary[toggle]; }
toggle = (discovered[now] == -1 ? 1 : 0);
for (int tmp : graph[now]) {
if (discovered[tmp] == 0) {
q.add(tmp);
discovered[tmp] = Binary[toggle];
} else if (discovered[tmp] == discovered[now])
return false;
}
}
return true;
}
Queue๋ฅผ ์ด์ฉํ์ฌ BFS ์ํ- ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ ๋ฐฉ๋ฌธ ์ฌ๋ถ ๊ฐ์ ๊ฐ์ง๊ณ ์๋
Binary๋ฐฐ์ด๊ณผtoggle๋ณ์๋ก setting - BFS ๋จ๊ณ๋ณ ์๋ก ๋ค๋ฅธ ๋ฐฉ๋ฌธ ๊ฐ ์ ์ฅ
- ๋ค์ ๋ฐฉ๋ฌธํ ์ ์ ์ด ์ด๋ฏธ ๋ฐฉ๋ฌธํ๊ณ , ํ์ฌ ๋ฐฉ๋ฌธ ์ ์ ๊ณผ ๊ฐ์ ๋ฐฉ๋ฌธ ๊ฐ์ ๊ฐ์ง๋ค๋ฉด ์ด๋ถ ๊ทธ๋ํ ๋ถ๊ฐ
๐ ํ๋ฆฐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.ArrayList;
import java.util.Scanner;
class Graph {
private final ArrayList<ArrayList<Integer>> graph;
private int[] discovered;
private boolean oddCycle = false;
private int dis;
public Graph(int size) {
this.graph = new ArrayList<>();
for (int i = 0; i <= size; i++) {
graph.add(new ArrayList<>());
}
}
public void DoubleAdd(int x, int y) {
graph.get(x).add(y);
graph.get(y).add(x);
}
public boolean isOddCycle(int s, int n) {
discovered = new int[20001];
dis = 1;
this.dfs(s, n);
return this.oddCycle;
}
public void dfs(int parent, int now) {
discovered[now] = dis++;
int size = graph.get(now).size();
if (size == 0) return;
for (int i = 0; i < size; i++) {
int idx = graph.get(now).get(i);
if (discovered[idx] == 0) {
this.dfs(now, idx);
}
else if (idx != parent && ((discovered[now] - discovered[idx])%2 == 0)) {
this.oddCycle = true;
}
}
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T > 0) {
int v = sc.nextInt();
int e = sc.nextInt();
sc.nextLine();
boolean isOdd = false;
Graph g = new Graph(v);
for (int i = 0; i < e; i++) {
String str = sc.nextLine();
int a = str.charAt(0) - '0';
int b = str.charAt(2) - '0';
g.DoubleAdd(a,b);
}
for (int i = 1; i <= v; i++) {
isOdd = g.isOddCycle(i, i);
// odd๊ฐ ํ ๋ฒ์ด๋ผ๋ true๋ฉด ์ด๋ถ ๊ทธ๋ํ๊ฐ ๋ ์ ์๋ค.
if (isOdd)
break;
}
if (!isOdd)
System.out.println("YES");
else
System.out.println("NO");
T-=1;
}
sc.close();
}
}
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Graph {
final List<Integer>[] graph;
final int[] Binary = { -1, 1 };
int[] discovered;
boolean isBinaryGraph = true;
int toggle = 0;
public Graph(int size) {
this.graph = new ArrayList[size+1];
discovered = new int[size+1];
for (int i = 0; i <= size; i++) {
graph[i] = new ArrayList<>();
}
}
public void DoubleAdd(int x, int y) {
graph[x].add(y);
graph[y].add(x);
}
public boolean solution() {
for (int i=1; i < graph.length; i++) {
if (graph[i].size() > 0 & discovered[i] == 0) {
isBinaryGraph = this.bfs(i);
if (!isBinaryGraph)
break;
}
}
return this.isBinaryGraph;
}
public boolean bfs(int parent) {
Queue<Integer> q = new LinkedList<>();
q.add(parent);
while (!q.isEmpty()) {
int now = q.poll();
if (discovered[now] == 0) { discovered[now] = Binary[toggle]; }
toggle = (discovered[now] == -1 ? 1 : 0);
for (int tmp : graph[now]) {
if (discovered[tmp] == 0) {
q.add(tmp);
discovered[tmp] = Binary[toggle];
} else if (discovered[tmp] == discovered[now])
return false;
}
}
return true;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T > 0) {
int v = sc.nextInt();
int e = sc.nextInt();
sc.nextLine();
Graph g = new Graph(v);
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
g.DoubleAdd(a,b);
}
if (g.solution())
System.out.println("YES");
else
System.out.println("NO");
T-=1;
}
sc.close();
}
}
โ๏ธ Review
- ๋
ผ๋ฆฌ๋ "DFS๋ฅผ ์ด์ฉํด ํ์๊ฐ์ ์ ์ ๋ผ๋ฆฌ ์ฌ์ดํด์ ์ด๋ฃจ๋ ๊ฒฝ์ฐ ์ด๋ถ๊ทธ๋ํ๊ฐ ๋ ์ ์๋ค" ์๊ณ , ๋ฐ๋ก๋ฅผ ํตํด ํ์ธํ์๋ ์ผ์ถ ๋ง๋ ๊ฒ ๊ฐ์ผ๋, ๊ณ์
๋ฐํ์ ์๋ฌ (IndexOutOfBounds)๊ฐ ๋ ์ ์ง์ ์ด ์์๋ค. -
10๋ฒ ์ด์์ ์๋ฌ๋ก ์ ์ ์ด ๋๊ฐ๋ฒ๋ฆด ๊ฒ ๊ฐ์ BFS๋ฅผ ์ด์ฉํ๋ ๋ฐฉ๋ฒ์ผ๋ก ๋ฐ๊ฟ๋ณด๊ธฐ๋ก ํ๋ค.
- BFS๋ฅผ ์ด์ฉํ๋ ๊ฒฝ์ฐ, ๋ฐฉ๋ฌธ ์์๋ก๋ ํด๊ฒฐํ ์ ์์ ๊ฒ ๊ฐ์ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ ๊ณ ์ํด์ผ ํ๋ค.
- DFS, BFS๋ฅผ ํ์คํ๊ฒ ์ดํดํ ์ ์์๋ ๊ฒ ๊ฐ๋ค.
String str = sc.nextLine();
int a = str.charAt(0) - '0';
int b = str.charAt(2) - '0';
- ์ ๋ฐฉ์์ผ๋ก
1 2ํ์์ ์ซ์๋ฅผ ์ ๋ ฅ๋ฐ์ผ๋10 12์ ๊ฐ์ ๊ฒฝ์ฐ ๋น์ฐํ ํ๋ฆด ์ ๋ฐ์ ์์๋ค ...